#include <iostream>
#include <string>
using namespace std;
int KMPStrMatching(string T,string P,int *N,int start)
{
    int j = 0;
    int i = start;
    int pLen = P.length();
    int tLen = T.length();
    if(tLen-start<pLen)
    {
        return -1;
    }
    while(j<pLen&&i<tLen)
    {
        if(j == -1||T[i] == P[j])
        {
            i++;
            j++;
        }
        else
            j = N[j];
    }
    if(j>=pLen)
        return (i-pLen);
    else
        return -1;
}
int * findNext(string P)
{
    int j,k;
    int m = P.length();//m为模式P的长度
    int *next = new int[m];//存放匹配特征向量next
    next[0] = -1;//匹配特征向量第一个元素为-1
    j = 0;k = -1;
    int temp;
    while(j<m-1)
    {
        while(k>=0&&P[k]!=P[j])
            k = next[k];
        j++;
        k++;
        next[j] = k;
    }
    return next;
}
int * findNextOpt(string P)
{ int j,k;
    int m = P.length();
    int *next = new int[m];
    next[0] = -1;
    j = 0;k = -1;
    int temp;
    while(j<m-1)
    {
        while(k>=0&&P[k]!=P[j])
            k = next[k];
        j++;
        k++;
        if(P[k] == P[j])
            next[j] = next[k];
        else
            next[j] = k;
    }
    return next;
}

int main() {
    string P = "abababb";
    string T = "ababababababb";
    int *n = findNextOpt(P);
    int r = KMPStrMatching(T,P,n,0);
    cout<<"r: "<<r<<endl;
    for(int i=r;i<T.length();i++)
    {

        cout<<T[i]<<" ";
    }
    delete [] n;
    return 0;
}
